package 算法.leetcode.sort;

import com.alibaba.fastjson.JSON;

/**
 * @author liclong
 * @create 2020-09-22 15:55
 * @desc 插入排序
 **/
public class InsertionSort {
    public static void main(String[] args) {
        int[] array = new int[]{2, 3, 1, 7, 4, 9, 6};
        insertionSort2(array, array.length);
        System.out.println(JSON.toJSONString(array));
    }


    /**
     * 插入排序【原地】【稳定】【O(n),O(n²)】
     *
     * 插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序
     *
     * @param array 待排序数组
     * @param n 数组大小
     */
    public static void insertionSort(int[] array, int n) {
        if (n <= 1) {
            return;
        }

        for (int i = 1; i < n; ++i) {
            // 取未排序区间的第一个元素
            int value = array[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                // 未排序区间的元素逐一与已排序区间元素比较
                if (array[j] > value) {
                    // 未排序区间元素后移一位到已排序区间
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            // 插入数据到已排序区间
            array[j + 1] = value;
        }
    }

    public static void insertionSort2(int[] array,int n){
        // 边界条件
        if (n<=1)return;
        for (int i=1;i<n;i++){
            // 记录要插入的数据, 后面被覆盖(如果没有比他小的,则不会覆盖)
            int insertValue = array[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j>0 && insertValue<array[j-1]){
                array[j] = array[j-1];
                j--;
            }
            //存在比其小的数 插入该插入的位置
            if (j!=i){
                array[j] = insertValue;
            }
        }
    }

}
